Thread-Safe & Lock-Free Structures

A single-threaded queue is a solved problem. Most candidates can write one half-asleep. Add threads and the floor tilts. That same push and pop, now racing on four or sixty-four cores, can shred the structure in ways that never reproduce on your laptop and surface once a month in a data center. This is the round where senior candidates pull away from the field. Anyone can wrap the whole thing in a lock. What the interviewer is listening for is whether you know what that lock is protecting you against, what it actually costs to hold, and what you reach for when that cost gets too high.

The bar has a name: correct under threads. "Ran on my machine" and "passed the test" don't count. A concurrent structure is correct only if every possible interleaving of every thread leaves it in a valid state, and there are a staggering number of interleavings. The whole discipline is learning to reason about the worst one instead of the lucky one. Watch how the round tends to escalate. It often opens with "make this queue thread-safe," and you reach for a mutex. Then the pressure arrives: now make it faster, now do it without a lock, now tell me the memory ordering, now what frees the node.

The Intel angle

At a chip company, "it worked when I ran it" won't fly, and the person across the table knows precisely why. A data race can lie dormant through a thousand runs because the timing never lined up. Then it fires the first time the code meets a machine with a different core count or a weaker memory model. Intel builds the cores and the threading libraries, so your interviewer has debugged the ugly version of this. When you claim a structure is thread-safe, expect "prove it." Walk two threads through the critical section one step at a time and show that no interleaving breaks the invariant. The signal is reasoning about the worst interleaving instead of the happy path.

IntelPremium lesson · System design round

The Intel design, worked end to end.

1. 1The design, drawn outSystem design · 1 diagram
2. 24 deep divesWith the tradeoffs

Get the Intel questions

$49 a year · all 100 companies · cancel anytime

From 20,000+ candidate reports, forum threads behind logins and write-ups in Chinese.

Read a free Intel lesson firstAlready a member? Sign in